home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part2 / 15489 < prev    next >
Encoding:
Text File  |  1996-08-05  |  2.4 KB  |  55 lines
  1. Path: news.halcyon.com!usenet
  2. From: normanb@halcyon.com (Norm Bryar)
  3. Newsgroups: comp.lang.c++
  4. Subject: Re: I need help with a data structure
  5. Date: Fri, 05 Apr 1996 16:23:33 GMT
  6. Organization: Northwest Nexus Inc.
  7. Message-ID: <4k3hcr$230@news.halcyon.com>
  8. References: <4k2fe8$cb9@newsource.ihug.co.nz>
  9. NNTP-Posting-Host: blv-pm2-ip12.halcyon.com
  10. X-Newsreader: Forte Free Agent 1.0.82
  11.  
  12. hoggy@ihug.co.nz (John Hogg) wrote:
  13.  
  14. >Hi, I'm quite new to programming so I would like some advice on a program
  15. >I'm going to write in C++.
  16.  
  17. >I have a number of chapters for a book, stored as text files (ie. all
  18. >ASCII characters). I need to 'read' through these chapters, then store
  19. >and display the new words that occur in each chapter so that a glossary
  20. >can be made for the key words. I also have a text file that contains 
  21. >common words that should be omitted (ie. "a", "the" etc). There are no
  22. >more than 1,000,000 words in each chapter and I estimate there will be 
  23. >no more than 30,000 different words.
  24.  
  25. >I have decided I should hash the words from the common word file into an
  26. >array.  Then, each word I read in from the chapters could be checked 
  27. >against this array and if it is not there I would hash it into another 
  28. >array of 30,000 items, discarding it if it is already there. Then this 
  29. >new word could be added to a binary tree to sort the words into 
  30. >alphabetical order for storage and display purposes.
  31.  
  32. >There is the added problem of words such as 'sweating' and æsweatÆ where
  33. >the word æsweatÆ would only be required.  I could simply check if a word 
  34. >has 'ing' on the end and remove it but then 'dancing' would become 'danc'.
  35. >Maybe it would be quicker to display all the words and get the user to 
  36. >delete the words not required.
  37.  
  38. >I would appreciate any help you can give me.
  39.  
  40. I thnk you're on the right track.  You may want a double-hash of the
  41. words you're collecting: this is a 3-D array, kind of, where you hash
  42. the word with one algorithm and, instead of finding a list, you find
  43. another hash-table.  You hash the word with this alternate algorithm
  44. and then find your list.  I think your hash searches may turn out
  45. faster if your number of buckets is square-rooted this way.
  46.  
  47. The 'ing' problem is known as word-stemming.  Perhaps some archie or
  48. web search for full-text-search or word-stemming will help you.
  49. Hopefully you can find the established rules that will tell you "if
  50. 'ing' preceeded by 'c', replace with 'e'" or something.
  51.  
  52. Good luck.
  53.                     --Norm 
  54.  
  55.